#include <stdio.h>
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* pre = NULL;
    struct ListNode* cur = head;
    while (cur != NULL) {
        // 拿到当前节点的下一个节点并保存起来
        struct ListNode* next = cur->next;
        // 让当前节点指向前一个节点
        cur->next = pre;
        // 让两个指针往前走
        pre = cur;
        cur = next;
    }
    return pre;
}
/**
 * 翻转 stack
 */
// struct ListNode* reverseList(struct ListNode* head) {
//     if (head == NULL || head->next == NULL) {
//         return head;
//     }
//     struct ListNode* stack[5001] = {};
//     int top = 0;
//     struct ListNode* curNode = head;
//     struct ListNode* res = head;  // 最终要换的头
//     while (curNode != NULL) {
//         if (curNode->next == NULL) {
//             res = curNode;
//         }
//         stack[top] = curNode;
//         top++;
//         curNode = curNode->next;
//     }
//     while (top > 0) {
//         // pop
//         struct ListNode* popNode = stack[top - 1];
//         if (top == 1) {
//             // 是否是栈中的最后一个元素
//             popNode->next = NULL;
//         } else {
//             popNode->next = stack[top - 2];
//         }
//         top--;
//     }
//     return res;
// }
